package src.BlueBridge.DeepRecursion;

/**
    问题描述:如果一个字符串包含两个相邻的重复字串，则称它为容易的串，其他串成为困难的串
    如:ABCDACABCAB，ABCDABCD都是容易的，D，DC，ABDAB,CBABCBA都是困难的

    输入正整数n,L，输出由前L个字符(大写英文字母)组成的，字典序第n小的困难的串
    例如，当L=3时，前7个困难的串分别为:
    A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA
    n指定为4的话，输出ABAC

    dfs每次都从整个串的头开始取
 */

public class _13困难的串 {
    public static void main(String[] args) {
        int n = 7;
        int l = 3;
        dfs(l, n, "");
    }

    static int count;

    public static void dfs(int l, int n, String prefix) {
        // 尝试在prefix后追加一个字符
        for (char i = 'A' ; i < 'A' + l ; i++) {
            // 如果是一个困难的串，就组合起来输出，并计数
            if (isHard(prefix, i)) {
                String x = prefix + i;
                System.out.println(x);
                // 计数器+1
                count++;
                if (count == n)
                    System.exit(0);
                dfs(l, n, x);
            }
        }
    }

    /**
     * 判断prefix+i是不是一个困难的串
     * 1.遍历所有的长度为偶数的子串，看是否对称
     * 2.prefix是一个困难的串，他之前的这个字符串本身就是一个困难的串了
     *   比如ABA，那么这个时候只需要考虑i位置，也就是最新加上的位置对整个串
     *   有没有影响，比如i和最后的A比较，Ai和前面的AB比较
     * @param prefix
     * @param i
     * @return
     */
    public static boolean isHard(String prefix, char i) {
        // 截取的宽度
        int count = 0;
        for (int j = prefix.length() - 1 ; j >= 0 ; j -= 2) {
            final String s1 = prefix.substring(j, j + count + 1);
            final String s2 = prefix.substring(j + count + 1) + i;
            if (s1.equals(s2))
                return false;
            count++;
        }
        return true;
    }
}
